package 面试题40_最小的k个数.实现一_类似快排思路;

import java.util.Random;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 12:11 2021/3/10
 * @Description：
 */
public class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {

        if (k<=0){
            return new int[0];
        }

        int start = 0, end = arr.length - 1;
        int index = partition(arr, start, end);

        while (index != k - 1) {
            if (index > k - 1) {
                end = index - 1;
                index = partition(arr, start, end);
            } else {
                start = index + 1;
                index = partition(arr, start, end);
            }
        }

        int[] result = new int[k];

        for (int ii = 0; ii < k; ii++) {
            result[ii] = arr[ii];
        }
        return result;
    }

    int partition(int[] data, int start, int end) {
        // 随机选取轴值索引
        int index = start + (int) ((new Random()).nextDouble() * (end - start + 1));
        int value = data[index];

        // 将轴值放到序列的第一个位置
        swap(data, start, index);

        int i = start, j = end;

        while (i < j) {
            while (i < j && value <= data[j]) {
                j--;
            }
            if (i < j) {
                swap(data, i, j);
            }
            while (i < j && value > data[i]) {
                i++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }

        return i;
    }

    void swap(int data[], int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
